#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""
    max match by max flow algorithm()
"""

from pprint import pprint
from max_flow import MaxFlow


class MaxMatch:
    SOURCE = 'source'
    SINK = 'sink'

    def __init__(self, edges):
        self.flow_edges = []
        is_bipartite = self.build_flow_edges(edges)

        print('=================== flow edge =====================')
        pprint(self.flow_edges)
        print('=================== flow edge =====================')

        if not is_bipartite:
            self.match = []
        else:
            max_flow = MaxFlow(self.flow_edges, self.SOURCE, self.SINK)

            removes = []
            for (start, end) in max_flow.edge_flow:
                if start == self.SOURCE or end == self.SINK:
                    removes.append((start, end))

            for edge in removes:
                del max_flow.edge_flow[edge]

            pprint(max_flow.edge_flow)
            # pass

    def build_flow_edges(self, edges):
        """

        :edges: TODO
        :returns: TODO

        """
        self.left = set()
        self.right = set()
        self.flow_edges = []        # (left, right, 1), "1" is weight

        for start, end in edges:
            if start in self.left:
                if end in self.left:
                    return False
                elif end in self.right:
                    # NOTE: 注意这里添加flow_edge
                    self.add_flow_edge(start, end)
                    continue
                else:
                    self.right.add(end)
                    self.add_flow_edge(start, end)
            elif start in self.right:
                if end in self.right:
                    return False
                elif end in self.left:
                    self.add_flow_edge(end, start)
                    continue
                else:
                    self.left.add(end)
                    self.add_flow_edge(end, start)
            else:
                if end in self.left:
                    self.right.add(start)
                    self.add_flow_edge(end, start)

                elif end in self.right:
                    self.left.add(start)
                    self.add_flow_edge(start, end)
                else:
                    self.left.add(start)
                    self.right.add(end)
                    self.add_flow_edge(start, end)

        self.add_source_sink()

        return True

    def add_flow_edge(self, start, end):
        self.flow_edges.append([start, end, 1])

    def add_source_sink(self):
        # source = 'source'
        for node in self.left:
            self.add_flow_edge(self.SOURCE, node)

        for node in self.right:
            self.add_flow_edge(node, self.SINK)


def main():
    print("start main")

    # edges = [(1,2), (2, 3), (3, 4), (4, 1)]
    # m = MaxMatch(edges)

    # 如果出现bug, 取最小的input调试
    edges = [
        ('Billy', 1),
        ('Billy', 4),

        ('Emily', 7),
        ('Emily', 3),
        ('Emily', 6),

        ('John', 2),
        ('John', 5),
        ('John', 4),

        ('Luke', 7),
        ('Luke', 2),

        ('Timothy', 7),
        ('Timothy', 6),
        ('Timothy', 5),

        ('Anna', 3),
        ('Anna', 6),

        ('Raj', 6),
        ('Raj', 7),
    ]
    m = MaxMatch(edges)

if __name__ == "__main__":
    main()
